﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using Xunit;
namespace LeetCode.CodeDay
{
    public partial class Code
    {
        public class ListNode
        {
            public int val;
            public ListNode next;
            public ListNode(int val = 0, ListNode next = null)
            {
                this.val = val;
                this.next = next;
            }
        }

        /// <summary>
        /// 删除链表的倒数第 N 个结点
        /// 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点
        /// </summary>
        /// <param name="head"></param>
        /// <param name="n"></param>
        /// <returns></returns>
        public ListNode RemoveNthFromEnd(ListNode head, int n)
        {
            List<int> list = new List<int>() { head.val };

            var next = head.next;
            while (next != null)
            {
                list.Add(next.val);
                next = next.next;
            }
            list.RemoveAt(list.Count - n);
            ListNode result = null;
            list.Reverse();
            foreach (var item in list)
            {
                result = new ListNode(item, result);
            }
            return result;
        }

        /// <summary>
        /// 有效的括号
        /// 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
        /// 有效字符串需满足：
        /// 左括号必须用相同类型的右括号闭合。
        /// 左括号必须以正确的顺序闭合。
        /// 每个右括号都有一个对应的相同类型的左括号
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public bool IsValidKuohao(string s)
        {
            Dictionary<char, char> dic = new Dictionary<char, char>() {
                { '[',']' },
                { '{','}' },
                { '(',')' },
            };
            int l = s.Length;

            for (int i = 0; i < l; i++)
            {
                if (dic.ContainsValue(s[i]))
                {
                    if (i == 0)
                        return false;
                    var preChar = dic.First(_ => _.Value == s[i]).Key;
                    if (dic.ContainsKey(s[i - 1]))
                    {
                        if (dic[s[i - 1]] != s[i])
                            return false;
                        else
                        {
                            s = s.Remove(i - 1, 2);
                            i -= 2;
                            l -= 2;
                        }
                    }
                    else
                        return false;

                }
            }
            return s.Length == 0;
        }
        /// <summary>
        /// 合并两个有序链表
        /// 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
        /// </summary>
        /// <param name="list1"></param>
        /// <param name="list2"></param>
        /// <returns></returns>
        public ListNode MergeTwoSortLists(ListNode list1, ListNode list2)
        {

            List<int> a1 = new List<int>();
            List<int> a2 = new List<int>();
            if (list1 != null)
            {
                a1.Add(list1.val);
                var next = list1.next;
                while (next != null)
                {
                    a1.Add(next.val);
                    next = next.next;
                }
            }
            if (list2 != null)
            {
                a2.Add(list2.val);
                var next = list2.next;
                while (next != null)
                {
                    a2.Add(next.val);
                    next = next.next;
                }
            }
            var all = a1.Concat(a2).OrderByDescending(_ => _).ToList();
            ListNode result = null;
            foreach (var iten in all)
            {
                if (result == null)
                {
                    result = new ListNode(iten);
                }
                else
                {
                    result = new ListNode(iten, result);
                }
            }
            return result;
        }
        /// <summary>
        /// 括号生成
        /// 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public IList<string> GenerateParenthesis(int n)
        {
            Dictionary<int, char> dic = new Dictionary<int, char>() {
                { 1,'('},
                { 2,')'}
            };
            string baseStr = "()";

            List<string> result = new List<string>() { "()" };
            if (n == 1)
                return result;
            for (int i = 1; i < n; i++)
            {
                var ss = new List<string>();
                for (int j = 0; j < result.Count; j++)
                {
                    for (int k = 0; k < result[j].Length; k++)
                    {
                        ss.Add(result[j].Insert(k, baseStr));
                    }
                }
                result = ss.Distinct().ToList();
            }

            return result;
        }
        /// <summary>
        /// 合并 K 个升序链表
        /// 给你一个链表数组，每个链表都已经按升序排列。
        /// 请你将所有链表合并到一个升序链表中，返回合并后的链表
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public ListNode MergeKLists(ListNode[] lists)
        {
            ListNode result = null;
            if (lists.Length == 0)
                return result;
            List<int> all = new List<int>();
            foreach (var list in lists)
            {
                if (list == null)
                    continue;
                List<int> d1 = new List<int> { list.val };
                var next = list.next;
                while (next != null)
                {
                    d1.Add(next.val);
                    next = next.next;
                }
                all.AddRange(d1);
            }
            all = all.OrderByDescending(_ => _).ToList();

            foreach (var item in all)
            {
                if (result == null)
                    result = new ListNode(item);
                else
                {
                    result = new ListNode(item, result);
                }
            }

            return result;
        }
        /// <summary>
        /// 两两交换链表中的节点
        /// 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）
        /// </summary>
        /// <param name="head"></param>
        /// <returns></returns>
        public ListNode SwapPairs(ListNode head)
        {
            if (head == null || head.next == null)
                return head;
            var second = head.next;
            var first = head;
            first.next = SwapPairs(second.next);
            second.next = first;
            return second;
        }

        /// <summary>
        /// K 个一组翻转链表
        /// </summary>
        /// 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
        /// k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
        /// 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换
        /// <param name="head"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public ListNode ReverseKGroup(ListNode head, int k)
        {
            if (head == null || head.next == null)
                return head;
            List<int> vals = new List<int>() { head.val };
            var next = head.next;
            while (next != null)
            {
                vals.Add(next.val);
                next = next.next;
            }
            for (int i = 0; i < (vals.Count - vals.Count % k); i += k)
            {
                for (int m = 0; m < k / 2; m++)
                {
                    var first = vals[i + m];
                    vals[i + m] = vals[i + k - m - 1];
                    vals[i + k - m - 1] = first;
                }
            }
            vals.Reverse();
            ListNode result = null;
            foreach (var item in vals)
            {
                if (result == null)
                {
                    result = new ListNode(item);
                }
                else
                {
                    result = new ListNode(item, result);
                }
            }
            return result;
        }
        /// <summary>
        /// 给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，
        /// 返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
        /// 考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
        /// 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
        /// 返回 k 。
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public int RemoveDuplicates(int[] nums)
        {
            if (nums == null || nums.Length == 0)
                return 0;
            if (nums.Length == 1)
                return 1;
            int i = 1;
            int max = 0;
            while (i != nums.Length)
            {
                if (nums[i] != nums[max])
                {
                    max++;
                    nums[max] = nums[i];
                }
                i++;
            }
            return max + 1;
        }

        /// <summary>
        /// 移除元素
        /// 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
        /// 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
        /// 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public int RemoveElement(int[] nums, int val)
        {
            if (nums == null || nums.Length == 0)
                return 0;
            int i = 0;
            int notEqual = 0;
            while (i != nums.Length)
            {
                if (nums[i] != val)
                {
                    nums[notEqual] = nums[i];
                    notEqual++;
                }
                i++;
            }

            return notEqual;
        }
        /// <summary>
        /// 找出字符串中第一个匹配项的下标
        /// </summary>
        /// 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。
        /// 如果 needle 不是 haystack 的一部分，则返回  -1 
        /// <param name="haystack"></param>
        /// <param name="needle"></param>
        /// <returns></returns>
        public int StrStr(string haystack, string needle)
        {
            int a1 = haystack.Length;
            int a2 = needle.Length;
            if (haystack == needle)
                return 0;
            if (a1 < a2)
                return -1;
            for (int i = 0; i < a1 - a2 + 1; i++)
            {
                if (haystack.Substring(i, needle.Length) == needle)
                    return i;
            }

            return -1;
        }
       
    }
}